package cn.fxzhang.leetcode.no01;

/**
 * 179. 最大数
 * 给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
 * 注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
 * 示例：
 * 输入：nums = [3,30,34,5,9]
 * 输出："9534330"
 * 提示：
 * 1 <= nums.length <= 100
 * 0 <= nums[i] <= 10^9
 *
 * 类型：数值处理
 * 题解：两两对比，如a、b、c，如ab>ba, ac>ca, 则a放在最前面
 * 时间复杂度：O(N^2)
 * 空间复杂度：O(N)
 *
 * 提交记录(1/3)：
 * 执行用时: 54 ms, 击败了5.16%
 * 内存消耗: 38.8 MB, 击败了5.02%
 * 第一次提交错误时解题思路不正确（过了1半数据）
 * 第二次提交错误是为考虑{0,0}的特例，返回了"00"
 * 【中等】通过次数82,574提交次数207,384
 * todo 速度慢了点
 * @author 张晓帆
 * @date 2021/4/12
 */
public class P0179_Largest_Number {

    public String largestNumber(int[] nums) {
        int n = nums.length;
        // f[i]表示nums[i]在跟其他数字进行两两组合时，nums[i]比其他数字更有价值的组合次数
        long sum = 0;
        int[] f = new int[n];
        for (int i=0; i<nums.length; i++){
            sum += nums[i];
            for (int j=i+1; j<nums.length; j++){
                if (compare(nums[i], nums[j])){
                    f[i]++;
                } else{
                    f[j]++;
                }
            }
        }
        if (sum == 0){
            return "0";
        }
        StringBuilder result = new StringBuilder();
        // 对f进行排序, f[i]越大，说明nums[i]放在前面的价值越大
        for (int i=0; i<n; i++){
            for (int j=i+1; j<n; j++){
                if (f[j] > f[i]){
                    int tmp = f[j];
                    f[j] = f[i];
                    f[i] = tmp;
                    tmp = nums[j];
                    nums[j] = nums[i];
                    nums[i] = tmp;
                }
            }
            result.append(nums[i]);
        }
        return result.toString();
    }

    /**
     * @param x
     * @param y
     * @return true：xy>yx
     */
    private boolean compare(int x, int y) {
        boolean flag = true;
        try {
            // a出异常，说明xy更大
            long a = Long.parseLong(x+""+y);
            // b出异常，说明yx更大
            flag = false;
            long b = Long.parseLong(y+""+x);
            return a>b;
        } catch (Exception e){
            // 当其中一位为10位数（10^9）,另一位为9,9999,9999时，会出异常
            return flag;
        }
    }
}
